As computer networks become increasingly more complex, more and more end stations communicate through more and more intermediate links. An intermediate link is typically a section of network cable with nodes or network switches at each end of the cable. A link can carry only a predetermined amount of network traffic, usually expressed as a bit per second limit. Network traffic is typically referred to as packets or cells, and each packet or cell requires a number of bits to be transmitted over the network.
For example, an intermediate link may carry traffic originating at numerous source end stations. And each source end station may be capable of generating network traffic at a rate in excess of what the intermediate link can handle without dropping packets. That is, each individual end station may be capable of driving an intermediate link into congestion. Accordingly, when a plurality of end stations are creating network traffic, and all of that traffic passes through a particular intermediate link, it is clear that a mechanism must be installed to limit the traffic created by the source end stations. Flow control is the generic term used to describe a mechanism to limit traffic created by source end stations.
Fairness in allocation of link capacity to various source end stations is another consideration which flow control must address. If one source end station uses the entire capacity of an intermediate link, then no other source end station can transmit. Congestion management systems provide each source end station with an opportunity to transmit, even though transmissions are at a rate reduced from what the source end station desires.
In many networks, particularly connection oriented networks, substantially stable routes are established for transfer of packets from a selected source end station to a selected destination end station. Typically, such stable routes are referred to as sessions or as virtual circuits. A virtual circuit is a path through intermediate links and nodes between a designated source end station and a designated destination end station. Each packet carries a designation of the virtual circuit, and each intermediate node maintains state information so that it can examine the virtual circuit designation in a received packet and accordingly forward the packet onto an appropriate downstream link.
Two common types of flow control typically utilized in networks having stable routes such as virtual circuits are, firstly, end-to-end flow control, and secondly, hop-by-hop flow control.
End-to-end flow control typically has a destination end station detect that congestion is occurring in the network. A destination end station may detect congestion by an intermediate node inserting a flag into a forwarded packet, where the flag informs the destination end station that the intermediate node's buffers are filling or that the intermediate node is otherwise experiencing congestion. The destination end station then places congestion information in an acknowledgement packet returned to the source end station, and the source end station reacts to the congestion information by reducing the rate which the source end station transmits packets onto the network.
A further refinement of end-to-end flow control is to transfer control packets along a virtual circuit from a source station, through the network to a destination station, and in response the destination station returns the control packet to the source station along the virtual circuit. As the control packet passes through the network, link capacity information is written into the control packet as it passes through each link of the virtual circuit. Each node at each link along the virtual circuit then maintains a table giving transmission rate information pertaining to each virtual circuit passing through that node.
Problems with a method of computing a transmission rate for each virtual circuit is that each intermediate node must keep a table containing state information for each virtual circuit passing through. Further, when a change occurs in the network, such as a new virtual circuit is established or an old virtual circuit is dropped, the network must respond rapidly to the change. Response to a change, in past attempts to apply end-to-end flow control, require a convergence time which is too long. For example, the worst case convergence time in many past systems is proportional to the number of virtual circuits, in addition to the dominant (or maximum) round trip time. Such long convergence times are not acceptable for efficient congestion management.
Secondly, hop-by-hop flow control is next discussed. In hop-by-hop flow control a downstream node uses a mechanism to inform an immediate upstream node to limit the rate at which the upstream node transmits packets to the downstream node. A typical mechanism used by the downstream node to limit the rate at which packets are transmitted by the upstream node, is the issuance of credits. Credits issued by the downstream node reflect the number of buffers in the downstream node. Credit information is sent in a control packet to the upstream node. The upstream node is permitted to send only the number of packets for which it has credits, and the upstream node decrements its credit count as it sends a packet. When the downstream node receives a packet the packet is stored in a buffer, and later the buffer is drained by the downstream node further processing the packet. As packets are forwarded by the downstream node, the downstream node sends credit information to the upstream node. Accordingly, the upstream node receives and uses credits to control the rate at which it transmits packets (or cells) to the downstream node. All of the nodes in the network use the hop-by-hop credit based flow control, and so permit their source stations to send only the number of packets which each node can handle.
Hop-by-hop flow control has been implemented by using either static buffering or dynamic buffering. In static buffering, sufficient buffers for each virtual circuit to fully occupy each link must be provided. Each individual virtual circuit may be capable of fully using the capacity of an intermediate link. Accordingly, each virtual circuit must have enough buffers assigned for it to fully use the capacity of the link. When many virtual circuits are established, the number of buffers needed becomes excessive. For example, in a transmission protocol referred to as Asynchronous Transfer Mode, or ATM, there are 24 bits assigned to designate a virtual circuit. Accordingly the number of possible virtual circuits is 2.sup.24. It is not practical to provide buffering at full link capacity for so many virtual circuits. And one never knows which of these virtual circuits will require buffering at full link capacity.
Secondly, when dynamic buffering is used, in a particular intermediate node, a pool of buffers is assigned for all of the virtual circuits passing through that node. Some of the buffers are allocated to each virtual circuit as they are needed. A problem is that when the network changes by adding or subtracting a virtual circuit, the system is very slow in responding to the change. For example, when a new virtual circuit is added, there may be no buffers available to be assigned to the new virtual circuit, as they may already be full from their previous assignment. The buffers drain slowly. Accordingly, the new virtual circuit must wait for a long time before it can begin transmission. Such long waits are unacceptable in efficient network management.
There is needed a flow control system capable of scaling to a large number of virtual circuits, capable of responding quickly to a change in the number of established virtual circuits, capable of responding to the different requirements of many different source end stations, and capable establishing a fair allocation of network resources to all of the source end stations.